class Node:
    def __init__(self,elem=-1,lchild=None,rchild=None):
        self.elem=elem
        self.lchild=lchild
        self.rchild=rchild

class Tree:
    def __init__(self):
        self.root=None
        self.queue=[]

    def insert(self,elem):
        new_node=Node(elem)
        self.queue.append(new_node)
        if self.root is None:#树空，新节点为根
            self.root=new_node
        else:
            if self.queue[0].lchild is None:#左孩子没有，新节点就是左孩子
                self.queue[0].lchild=new_node
            elif self.queue[0].rchild is None:#否则判断右孩子
                self.queue[0].rchild = new_node
                self.queue.pop(0) #队头出队，下一个queue[0]又是队头了，他就是下一次判断的对象

    def pre_order(self,current_node:Node):
        if current_node:
            print(current_node.elem,end='')
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)

    def mid_order(self,current_node:Node):
        if current_node:
            self.mid_order(current_node.rchild)
            print(current_node.elem, end='')
            self.mid_order(current_node.lchild)

    def last_order(self,current_node:Node):
        if current_node:
            self.last_order(current_node.lchild)
            self.last_order(current_node.rchild)
            print(current_node.elem, end='')


if __name__ == '__main__':
    tree=Tree()
    for i in range(1,10):
        tree.insert(i)

    tree.pre_order(tree.root)
    print()
    tree.mid_order(tree.root)
    print()
    tree.last_order(tree.root)